package complexdatastructure.multidatastructure;

import java.util.*;

/**
 * @Classname : RandomizedSet
 * @Description :
 * <a href="https://leetcode.cn/problems/insert-delete-getrandom-o1/">380. O(1) 时间插入、删除和获取随机元素</a>
 * @Author : chentianyu
 * @Date 2023/2/12 21:38
 */


public class RandomizedSet {

    private List<Integer> list;  // 列表存储元素
    private Map<Integer, Integer> map;  // 元素：列表位置
    private int size;
    private Random random;

    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        size = 0;
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;

        list.add(val);
        map.put(val, size++);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        // 将末尾位置移到目标位置，再删除末尾位置元素
        int targetIndex = map.get(val);
        int lastVal = list.get(--size);
        list.set(targetIndex, lastVal);  // 列表中将末尾元素移至目标位置
        map.put(lastVal, targetIndex);  // map中更新原末尾元素再列表中位置
        list.remove(size);  // 列表删除末尾位置元素
        map.remove(val);  // map中删除目标元素
        return true;
    }

    public int getRandom() {
        int ran = random.nextInt(size);
        return list.get(ran);
    }
}
